package com.company.剑指offer每日刷题.专项版;

/**
 * 剑指 Offer II 005. 单词长度的最大乘积
 * 给定一个字符串数组words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。
 * <p>
 * 示例1:
 * 输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"]
 * 输出: 16
 * 解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/aseY1I
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MaxProduct {
    public static void main(String[] args) {
        MaxProduct obj = new MaxProduct();
        int i = obj.maxProduct(new String[]{"a", "aa", "aaa", "aaaa"});
        System.out.println(i);
    }

    /**
     * 1.暴力穷举法：
     * 就是遍历穷举所有的组合，并且对这些字符串组合通过循环遍历，比较它们是否为无重复字符的字符串对，进行长度的积。
     * 时间复杂度：0(n^3)  ：时间复杂度劝退
     * <p>
     * 2.二进制判断重复法
     * 思路：（1）将一个字符串中是否包含某一个字母的两种状态用int二进制中固定的数位的来表示。得到一个整状态值num
     * （2）将两个字符串的所对应状态值进行&运算，为0表示无重复，不为0表示有重复。这样一来，对于两个字符串是否包含重复字符的计算转化为了对两个整型的与运算。
     * 时间复杂度： O(n^2)
     */
    public int maxProduct(String[] words) {
        int[] states = new int[words.length];
        //计算状态值
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words[i].length(); j++) {
                states[i] |= (1 << (words[i].charAt(j) - 'a'));
            }
        }
        int res = 0;
        //判断是否无重复并求乘积
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if ((states[i] & states[j]) == 0) {
                    res = Math.max(words[i].length() * words[j].length(), res);
                }
            }
        }
        return res;
    }
}
